package offer.day5;

public class No8getNext {
    /*
     *面试题8：二叉树的下一个节点
     *题目：给定一棵二叉树和其中的一个节点，如何找到中序遍历序列的下一个节点？
     *    树中的节点除了有两个分别指向左、右子节点的指针 ，还有一个指向父节点的指针。
     *
     *    总结一下，下一个节点可能出现的位置:
     *    1.若这一节点有右子树，则它下一个节点就是它右子树的最左子节点
     *    2.若这一节点没有右子树，但是它是父节点的左子节点，则它下一个节点就是它的父节点
     *    3.若这一节点（节点A）没有右子树，且是父节点的右子节点，
     *         那就沿着它（节点A）的父节点（节点B）一直往上找，。。。
     *         直到找到一个节点（节点C）是其（节点C）父节点的左子节点（若有这样的节点），
     *         则它下一个节点就是  找到的这个节点（节点C）的父节点
     *         若无这样的节点，则它下一个节点为null
     *   （2情况其实是3的特殊情况  刚好其父节点就是左子节点）
     * */
    public static void main(String[] args) {
        TreeNode_p a = new TreeNode_p(1);
        TreeNode_p b = new TreeNode_p(2);
        TreeNode_p c = new TreeNode_p(3);
        TreeNode_p d = new TreeNode_p(4);
        TreeNode_p e = new TreeNode_p(5);
        TreeNode_p f = new TreeNode_p(6);
        TreeNode_p g = new TreeNode_p(7);
        TreeNode_p h = new TreeNode_p(8);
        TreeNode_p i = new TreeNode_p(9);

        //构造二叉树
        a.left = b;
        a.right = c;

        b.left = d;
        b.right = e;
        b.parent = a;

        c.left = f;
        c.right = g;
        c.parent = a;

        d.parent = b;

        e.left = h;
        e.right = i;
        e.parent = b;

        f.parent = c;
        g.parent = c;

        h.parent = e;
        i.parent = e;

        No8getNext getNext = new No8getNext();
        TreeNode_p next = getNext.findNext(a);
        if (next != null) {
            System.out.println("a节点的下一个节点值为" + next.val);
        } else
            System.out.println("a节点无下一个节点");
    }

    public TreeNode_p findNext(TreeNode_p root){
        if(root==null) return null;
        if(root.right!=null){
            root=root.right;
            while(root.left!=null){
                root=root.left;
            }
            return root;
        }else{
            while(root.parent!=null){
                if(root.parent.left==root){
                    return root.parent;
                }
                root=root.parent;
            }
        }
        return null;
    }

}

class TreeNode_p{
    int val;
    TreeNode_p left;
    TreeNode_p right;
    TreeNode_p parent;

    TreeNode_p(int val){
        this.val=val;
    }

    @Override
    public String toString() {
        return "TreeNode_p{" +
                "val=" + val +
                "}";
    }
}
